<html>
 <head>
  <link href="./leetcode-problem.css" rel="stylesheet" type="text/css">
 </head>
 <body>
  <div class="question_difficulty">
   难度：Medium
  </div>
  <div>
   <h1 class="question_title">
    147. Insertion Sort List
   </h1>
   <p>
    Sort a linked list using insertion sort.
   </p>
   <ol>
   </ol>
   <p>
    <img alt="" src="https://upload.wikimedia.org/wikipedia/commons/0/0f/Insertion-sort-example-300px.gif" style="height:180px; width:300px">
    <br>
    <small>
     A graphical example of insertion sort. The partial sorted list (black) initially contains only the first element in the list.
     <br>
     With each iteration one element (red) is removed from the input data and inserted in-place into the sorted list
    </small>
    <br>
    &nbsp;
   </p>
   <ol>
   </ol>
   <p>
    <strong>
     Algorithm of Insertion Sort:
    </strong>
   </p>
   <ol>
    <li>
     Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list.
    </li>
    <li>
     At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there.
    </li>
    <li>
     It repeats until no input elements remain.
    </li>
   </ol>
   <p>
    <br>
    <strong>
     Example 1:
    </strong>
   </p>
   <pre>
<strong>Input:</strong> 4-&gt;2-&gt;1-&gt;3
<strong>Output:</strong> 1-&gt;2-&gt;3-&gt;4
</pre>
   <p>
    <strong>
     Example 2:
    </strong>
   </p>
   <pre>
<strong>Input:</strong> -1-&gt;5-&gt;3-&gt;4-&gt;0
<strong>Output:</strong> -1-&gt;0-&gt;3-&gt;4-&gt;5
</pre>
  </div>
  <div>
   <h1 class="question_title">
    147. 对链表进行插入排序
   </h1>
   <p>
    对链表进行插入排序。
   </p>
   <p>
    <img alt="" src="https://upload.wikimedia.org/wikipedia/commons/0/0f/Insertion-sort-example-300px.gif">
    <br>
    <small>
     插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。
     <br>
     每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。
    </small>
   </p>
   <p>
    &nbsp;
   </p>
   <p>
    <strong>
     插入排序算法：
    </strong>
   </p>
   <ol>
    <li>
     插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
    </li>
    <li>
     每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
    </li>
    <li>
     重复直到所有输入数据插入完为止。
    </li>
   </ol>
   <p>
    &nbsp;
   </p>
   <p>
    <strong>
     示例 1：
    </strong>
   </p>
   <pre><strong>输入:</strong> 4-&gt;2-&gt;1-&gt;3
<strong>输出:</strong> 1-&gt;2-&gt;3-&gt;4
</pre>
   <p>
    <strong>
     示例&nbsp;2：
    </strong>
   </p>
   <pre><strong>输入:</strong> -1-&gt;5-&gt;3-&gt;4-&gt;0
<strong>输出:</strong> -1-&gt;0-&gt;3-&gt;4-&gt;5
</pre>
  </div>
 </body>
</html>